/**
 * 
 */
package leetCode;

import java.util.ArrayList;

/**
 * @author zhong
 *
 */
public class StreamofCharacters {

	public StreamofCharacters(String[] words) {
		root = new Node();
		for (int i = 0; i < words.length; i++) {
			max_len = Math.max(max_len, words[i].length());
			insert(root, reverse(words[i]));
		}
		queue = new ArrayList();
	}

	class Node {
		Node[] childs = new Node[26];
		boolean isEnd = false;
	}

	private void insert(Node root2, String reverse) {
		Node cur = root2;
		for (int i = 0; i < reverse.length(); i++) {
			char ch = reverse.charAt(i);
			int index = ch - 'a';
			if (cur.childs[index] == null) {
				cur.childs[index] = new Node();
			}
			cur = cur.childs[index];
		}
		cur.isEnd = true;
	}

	private String reverse(String string) {
		StringBuilder stringBuilder = new StringBuilder(string);
		return stringBuilder.reverse().toString();
	}

	Node root;
	int max_len;
	ArrayList<Character> queue;

	public boolean query(char letter) {
		queue.add(letter);
		Node cur = root;
		for (int i = queue.size() - 1; i >= 0; i--) {
			char ch = queue.get(i);
			int index = ch - 'a';
			if (cur.childs[index] == null) {
				return false;
			}
			if (cur.childs[index].isEnd) {
				return true;
			}
			cur = cur.childs[index];
		}
		return false;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String[] words = { "cd", "f", "kl" };
		StreamofCharacters streamofCharacters = new StreamofCharacters(words);
		for (char i = 'a'; i < 'm'; i++) {
			System.out.println(streamofCharacters.query(i));
		}
	}

}
